package com.chenxys.algorithm.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/find-maximum-number-of-string-pairs/">最大字符串配对数目</a><br/>
 *      给你一个下标从 0 开始的数组 words ，数组中包含 互不相同 的字符串。<br/>
 *      如果字符串 words[i] 与字符串 words[j] 满足以下条件，我们称它们可以匹配：<br/>
 *      字符串 words[i] 等于 words[j] 的反转字符串。<br/>
 *      0 <= i < j < words.length<br/>
 *      请你返回数组 words 中的 最大 匹配数目。<br/>
 *      注意，每个字符串最多匹配一次。<br/>
 *      例: <br/>
 *          输入：words = ["cd","ac","dc","ca","zz"]<br/>
 *          输出：2<br/>
 *          解释：在此示例中，我们可以通过以下方式匹配 2 对字符串：<br/>
 *              - 我们将第 0 个字符串与第 2 个字符串匹配，因为 word[0] 的反转字符串是 "dc" 并且等于 words[2]。<br/>
 *              - 我们将第 1 个字符串与第 3 个字符串匹配，因为 word[1] 的反转字符串是 "ca" 并且等于 words[3]。<br/>
 *              可以证明最多匹配数目是 2 。<br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/10 10:07
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode2744 {

    /**
     * <p>
     *     最大字符串配对数目 hash
     * </p>
     * @param words 字符串数组
     * @return 能匹配的最大值
     */
    public static int maximumNumberOfStringPairs(String[] words) {
        int n = words.length;
        int ans = 0;
        Set<Integer> seen = new HashSet<Integer>();
        for (int i = 0; i < n; ++i) {
            if (seen.contains(words[i].charAt(1) * 100 + words[i].charAt(0))) {
                ++ans;
            }
            seen.add(words[i].charAt(0) * 100 + words[i].charAt(1));
        }
        return ans;
    }

    /**
     * <p>
     *     最大字符串配对数目 遍历
     * </p>
     * @param words 字符串数组
     * @return 能匹配的最大值
     */
    public static int checkMaximumNumberOfStringPairs(String[] words) {
        int N = words.length;
        int maxVal = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; ++j) {
                // 首 == 尾                                               尾  == 首
                if (words[i].charAt(0) == words[j].charAt(1) && words[i].charAt(1) == words[j].charAt(0)) {
                    maxVal++;
                }
            }
        }
        return maxVal;
    }
}
